💰 Coin Change II - Number of Ways

Find the number of ways to make a target sum using coins with infinite supply

👩‍💻 Coin Combination Challenge

🎯 The Mission:

Determine the number of ways to make a target sum using an infinite supply of given coin denominations with dynamic programming.

📋 Requirements:

  • Count combinations to form the target sum
  • Use coins with infinite supply
  • Each coin has a denomination value
  • Output the total number of ways

Input/Output Specifications

  • Input: n (number of coin types), n coin denominations, s (target sum)
  • Output: Number of ways to make sum s (integer)
  • Constraints: 1 ≤ n ≤ 100, 1 ≤ coins[i] ≤ 1000, 1 ≤ s ≤ 1000

Example 1: n=3, coins=[1,2,3], s=3

Coins:

1
2
3

Output: 3

Example 2: n=3, coins=[1,2,3], s=4

Coins:

1
2
3

Output: 4

⚡ Dynamic Programming Explained

How Dynamic Programming Works for Coin Change II

  1. Initialize: Create a DP array where dp[j] is the number of ways to make sum j
  2. Base Case: Set dp[0] = 1 (one way to make sum 0: no coins)
  3. Iterate Coins: For each coin, update dp[j] by adding dp[j - coin] for all j from coin to s
  4. Output: dp[s] gives the total number of ways

Example DP Table (n=2, coins=[1,2], s=3)

Sum0123
After coin 11111
After coin 21122

Output: 2 (ways: [1,1,1], [1,2])

Time Complexity

O(n * s)

Iterate over n coins and s sums

Space Complexity

O(s)

For the DP array

Why Dynamic Programming?

  • ✅ Efficiently counts all combinations
  • ✅ Handles infinite coin supply
  • ✅ Avoids redundant calculations
  • ❌ Requires careful initialization

🔍 Step-by-Step Dynamic Programming Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input coins and sum
2. Initialize DP array
3. Process coins
4. Display result

Current Coins:

DP Table:

🎮 Practice Coin Change II

Enter inputs, then click "Compute Number of Ways"

Test Cases

Example 1: n=3, coins=[1,2,3], s=3 → 3

Example 2: n=3, coins=[1,2,3], s=4 → 4

📊 Algorithm Analysis

Dynamic Programming Process

  1. Initialize: Set dp[0] = 1, others to 0
  2. Iterate Coins: For each coin, update dp[j] += dp[j - coin] for j from coin to s
  3. Output: dp[s] as the number of ways

Time Complexity

O(n * s)

Iterate over n coins and s sums

Space Complexity

O(s)

For the DP array

Key Points

  • Dynamic Programming: Builds solutions incrementally
  • Infinite Supply: Allows reusing coins
  • Applications: Currency systems, combinatorial problems
  • Limitation: Large s increases space usage